|
|
Demonstrace rozptýlených gramatik s jediným kontextovým pravidlem
Holas, David ; Klobučníková, Dominika (oponent) ; Křivka, Zbyněk (vedoucí práce)
Práce se zabývá tvorbou aplikace, která ze zadané frontové gramatiky konstruuje gramatiku s rozptýleným kontextem a jedním kontextovým pravidlem, derivuje v~ní zadaný řetězec a celý proces prezentuje uživateli. K derivaci řetězců byla navržena heuristika, která snižuje počet aplikovatelných pravidel v každé větné formě. Uživatel může ovlivnit průběh derivace ručním výběrem pravidel. Průběh derivace je vypisován v podobě čistého textu nebo HTML dokumentu. Byly odhaleny dvě chyby v teoretickém podkladu práce, jmenovitě v převodu frontové gramatiky do 1. normální formy a v konstrukci gramatik s rozptýleným kontextem a jedním kontextovým pravidlem. V práci se podařilo nalézt částečné řešení druhého problému, které je implementováno v aplikaci.
|
|
|
Omezení větných forem gramatik s rozptýleným kontextem
Šimáček, Jiří ; Masopust, Tomáš (oponent) ; Meduna, Alexandr (vedoucí práce)
Tato práce zavádí pojem zobecněných gramatik s rozptýleným kontextem, které se od tradičních liší tím, že levé strany pravidel mohou obecně obsahovat řetězec neterminálních symbolů namísto jediného neterminálu. Dále jsou studovány dva typy omezení při větné derivaci v těchto gramatikách. Nechť k je konstanta. První omezení požaduje, aby přepsání všech symbolů nastalo mezi prvními k symboly v prvním souvislém bloku neterminálů ve větné formě v každém derivačním kroku. Druhé omezení definuje derivaci pouze nad větnými formami, které obsahují nejvýše k výskytů neterminálů. Jako hlavní výsledek práce demonstruje, že oba typy omezení snižují vyjadřovací sílu na úroveň bezkontextových gramatik.
|
|
|
New Versions of Classical Automata and Grammars
Soukup, Ondřej ; Solár, Peter (oponent) ; Meduna, Alexandr (vedoucí práce)
This master's thesis investigates new versions of automata and grammars and is thus divided into two parts. First part defines and studies pure multi-pushdown automata and additionally introduces total orders above their pushdowns or pushdown symbols. Present work proves, defined restrictions decrease accepting power of these automata. In the second part, new modes of scattered context derivations are defined and described, which generalize the relation of direct derivation. It is proved, these modes do not decrease the generation power of scattered context grammars.
|
|
|
Retargetable Analysis of Machine Code
Křoustek, Jakub ; Janoušek, Jan (oponent) ; Návrat,, Pavol (oponent) ; Kolář, Dušan (vedoucí práce)
Program analysis is a computer-science methodology whose task is to analyse the behavior of a given program. The methods of program analysis can also be used in other methodologies such as reverse engineering, re-engineering, code migration, etc. In this thesis, we focus on program analysis of a machine-code and we address the limitations of a nowadays approaches by proposing novel methods of a fast and accurate retargetable analysis (i.e. they are designed to be independent of a particular target platform). We focus on two types of analysis - dynamic analysis (i.e. run-time analysis) and static analysis (i.e. analysing application without its execution). The contribution of this thesis within the dynamic analysis lays in the extension and enhancement of existing methods and their implementation as a retargetable debugger and two types of a retargetable translated simulator. Within the static analysis, we present a concept and implementation of a retargetable decompiler that performs a program transformation from a machine code into a human-readable form of representation. All of these tools are based on several novel methods defined by the author. According to our experimental results and users feed-back, all of the proposed tools are at least fully competitive to existing solutions, while outperforming these solutions in several ways.
|
|
|
Formal Models of Distributed Computation
Soukup, Ondřej ; Horváth,, Géza (oponent) ; Rogalewicz, Adam (oponent) ; Meduna, Alexandr (vedoucí práce)
The present thesis introduces derivation trees for several different types of grammars in generalized Kuroda normal forms; namely, general, regular-controlled, and scattered context grammars and cooperating distributed grammar systems. It defines simple tree-based properties related to non-context-free properties of all grammars in question and shows that if there exists a limiting constant k such that every sentence in the generated language L is the frontier of a derivation tree in which the number of occurrences of the defined tree-based properties is limited by k, the language L is in fact context-free. The thesis explains that this result represents a powerful tool for showing languages to be context-free. It also provides illustrations and examples which sketch how to apply this tool in practice.
|
|
| |
|
|
Transformace frontových gramatik
Holas, David ; Regéciová, Dominika (oponent) ; Křivka, Zbyněk (vedoucí práce)
Diplomová práce je rozdělena do dvou částí. První část spočívá v opravě chyby v algoritmickém převodu frontové gramatiky do 1. normální formy navrženém jiném odborném článku. Algoritmus byl analyzován a úspěšně opraven. Druhá část se zabývá návrhem nové transformace na gramatiky s rozptýleným kontextem s omezenou popisnou složitostí. Práce obsahuje důkaz její korektnosti a studium její složitosti. Byla vytvořena konzolová aplikace, která pomáhá automaticky analyzovat příslušné transformace.
|
|
|
Demonstrace rozptýlených gramatik s jediným kontextovým pravidlem
Holas, David ; Klobučníková, Dominika (oponent) ; Křivka, Zbyněk (vedoucí práce)
Práce se zabývá tvorbou aplikace, která ze zadané frontové gramatiky konstruuje gramatiku s rozptýleným kontextem a jedním kontextovým pravidlem, derivuje v~ní zadaný řetězec a celý proces prezentuje uživateli. K derivaci řetězců byla navržena heuristika, která snižuje počet aplikovatelných pravidel v každé větné formě. Uživatel může ovlivnit průběh derivace ručním výběrem pravidel. Průběh derivace je vypisován v podobě čistého textu nebo HTML dokumentu. Byly odhaleny dvě chyby v teoretickém podkladu práce, jmenovitě v převodu frontové gramatiky do 1. normální formy a v konstrukci gramatik s rozptýleným kontextem a jedním kontextovým pravidlem. V práci se podařilo nalézt částečné řešení druhého problému, které je implementováno v aplikaci.
|
|
|
Formal Models of Distributed Computation
Soukup, Ondřej ; Horváth,, Géza (oponent) ; Rogalewicz, Adam (oponent) ; Meduna, Alexandr (vedoucí práce)
The present thesis introduces derivation trees for several different types of grammars in generalized Kuroda normal forms; namely, general, regular-controlled, and scattered context grammars and cooperating distributed grammar systems. It defines simple tree-based properties related to non-context-free properties of all grammars in question and shows that if there exists a limiting constant k such that every sentence in the generated language L is the frontier of a derivation tree in which the number of occurrences of the defined tree-based properties is limited by k, the language L is in fact context-free. The thesis explains that this result represents a powerful tool for showing languages to be context-free. It also provides illustrations and examples which sketch how to apply this tool in practice.
|
|
|
Retargetable Analysis of Machine Code
Křoustek, Jakub ; Janoušek, Jan (oponent) ; Návrat,, Pavol (oponent) ; Kolář, Dušan (vedoucí práce)
Program analysis is a computer-science methodology whose task is to analyse the behavior of a given program. The methods of program analysis can also be used in other methodologies such as reverse engineering, re-engineering, code migration, etc. In this thesis, we focus on program analysis of a machine-code and we address the limitations of a nowadays approaches by proposing novel methods of a fast and accurate retargetable analysis (i.e. they are designed to be independent of a particular target platform). We focus on two types of analysis - dynamic analysis (i.e. run-time analysis) and static analysis (i.e. analysing application without its execution). The contribution of this thesis within the dynamic analysis lays in the extension and enhancement of existing methods and their implementation as a retargetable debugger and two types of a retargetable translated simulator. Within the static analysis, we present a concept and implementation of a retargetable decompiler that performs a program transformation from a machine code into a human-readable form of representation. All of these tools are based on several novel methods defined by the author. According to our experimental results and users feed-back, all of the proposed tools are at least fully competitive to existing solutions, while outperforming these solutions in several ways.
|
host ::
RSS.